/*
	本快速排序参考了编程珠玑
	本位结构参考了编程珠玑
	感谢编程珠玑，对我有很大的帮助！
*/

#include <stdio.h>
#include <stdlib.h>
int Get(int [],int,int);
void sort(int p[],int l,int u)
{
	int t=0,r,i=1,j=u;
	if(u-l<1) return;
	r=randint(l,u);
	t=p[l];p[l]=p[r];p[r]=t;
	t=p[l];
	while(1){
		while(i<=u&&p[i]<=t) i++;
		while(j>l&&p[j]>=t)	 j--;
		if(i>=j) break;
		t=p[i];p[i]=p[j];p[j]=t;
	}
	t=p[l];p[l]=p[j];p[j]=t;
	sort(p,l,j-1);
	sort(p,j+1,u);
}	//快速排序

int randint(int a,int b)	{
	return rand()%(b-a)+a;
}	//排序中的随机函数

int Get(int w[],int Min,int i){
	i-=2*Min;
	if(i<=0) return 0;
	return w[i>>5]&(1<<(i&0x1F));
}

int Create(int p[],int n){
	int i,j,t,*w,s;
	t=(p[n-1]-p[0])/32+1;//此处应该+1
	s=2*p[0];
	w=(int *)malloc(sizeof(int)*t);		
	for(i=0;i<t;i++)w[0]=0;
	for(i=0;i<n-1;i++)	{
		for(j=i+1;j<n;j++){
			t=p[i]+p[j];
			if(t<=p[n-1]&&t>=s){
				t=t-s;
				w[t>>5] |= (1<<(t&0x1F)); 
			}	
		}//如果t>=s会有溢出错误
		if(Get(w,p[0],p[i+2])){
			printf("YES\n");
			if(p)	free(p);
			if(w) free(w);
		return 1;		
		}
		if((p[i+1]+p[i+2]>p[n-1])) return 0;	
	}
	return 0;
}
